Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving
无需重新求解的资源自适应随机梯度下降在线线性规划
🧭 在线线性规划 · 资源自适应SGD
Department of Management Science, School of Management, Fudan University
提出RASGD，用O(m)一阶SGD更新资源价格，避免重求解LP，达到O(log T) regret
📌 工作参考价值（4 点）
- 在电商/广告资源约束分配场景（如预算、库存、LLM推理算力配额），可用一阶SGD替代per-arrival LP重求解，每到达仅O(m)时间与内存，适合高并发实时决策。
- 步长策略可借鉴：早期小步长学习资源价格，后期增大步长以快速响应库存消耗，无需人工调参，在不同资源消耗阶段自适应。
- 算法在标准非退化条件下每条样本路径可行，并达到O(log T) regret，适合对安全性和长期收益都有要求的在线广告投放、流量分配系统。
- 适用于LLM推理服务中的资源定价：每个请求到达时根据剩余算力/令牌配额动态更新影子价格，指导准入或资源预留，无需离线求解大规模LP。